package com.linwen.excise.base;

/**
 * @author : linwen
 * @date : 下午11:27 2021/9/26
 */
/*
 * 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *
 * 思路：夹逼法，横向大往小走  纵向小往大走
 * */
public class _04二维数组中的查找 {

    public static void main(String[] args) {
        int[][] arr = new int[][] {{1,2,8,9},
                {2,4,9,12},
                {4,7,10,13},
                {6,8,11,15}};
        int t = 5;
        System.out.print(Find(t,arr));
    }

    private static boolean Find(int t, int[][] arr) {
        int i = arr.length;
        int j = arr[0].length;
        for(int m=i-1,n=0;m>=0&&n<j;) {
            if(t>arr[m][n]) {
                n++;
                continue;
            }else if(t<arr[m][n]) {
                m--;
                continue;
            }
            if(t==arr[m][n]) {
                return true;
            }
        }
        return false;
    }
}